// 接水滴

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>

// 方向枚举
typedef enum
{
    LEFT = 0,
    RIGHT = 1,
    UP = 2,
    DOWN = 3,
    UNKNOWN = 4
} direction_e;

int trap(uint32_t *height, int n)
{

    printf("trap raw : ");
    for (uint32_t i = 0; i < n; i++)
    {
        printf("%d ", height[i]);
    }
    printf("\n");

    // 数据清洗

    // 找出第一个非0的元素
    uint32_t lIndex = 0,
             rIndex = 0,
             dataLen = 0;
    for (uint32_t i = 0; i < n; i++)
    {
        if (height[i] > 0)
        {
            // 丢掉首次掉高度递加的元素
            if (height[i] < height[i + 1])
            {
                continue;
            }
            lIndex = i;
            break;
        }
    }

    // 找出末尾非0的元素
    for (uint32_t i = n - 1; i > 0; i--)
    {
        // printf("%d %d ", i, height[i]);
        if (height[i] > 0)
        {
            // 丢掉末尾第一次高度递减的元素
            if (height[i - 1] > height[i])
            {
                continue;
            }
            rIndex = i;
            break;
        }
    }

    printf("lIndex %d rIndex %d\n", lIndex, rIndex);

    dataLen = rIndex - lIndex + 1;

    // 保存新的结果
    uint32_t *heightNew = (uint32_t *)malloc(sizeof(uint32_t) * dataLen);
    if (heightNew == NULL)
    {
        return -1;
    }
    memset(heightNew, 0, sizeof(uint32_t) * dataLen);
    memcpy(heightNew, height + lIndex, sizeof(uint32_t) * dataLen);

    uint32_t countDown = 0,
             CountUp = 0;

    // 找出可以存放水滴的位置
    for (uint32_t i = 0; i < dataLen; i++)
    {
        printf("%d ", heightNew[i]);

        if (heightNew[i] > heightNew[i + 1] && i < dataLen)
        {
            countDown++;
        }
        else
        {
            CountUp++;
        }
    }
    printf("\n");

    free(heightNew);
    heightNew = NULL;

    printf("countDown %d CountUp %d\n", countDown, CountUp);

    return countDown - CountUp;
}

int trap2(uint32_t *height, int n)
{
    int32_t cout = 0, temp = 0, leftIndex = 0, rightIndex = 0;
    for (int32_t i = 0; i < n; i++)
    {
        if (height[i] > 0)
        {
            if (height[i] > height[i + 1])
            {
                leftIndex = i;
                break;
            }
        }
    }

    for (int32_t i = n - 1; i > 0; i--)
    {
        if (height[i] > 0)
        {
            if (height[i - 1] < height[i])
            {
                rightIndex = i;
                break;
            }
        }
    }

    printf("leftIndex %d rightIndex %d\n", leftIndex, rightIndex);
    for (int32_t i = leftIndex; i < rightIndex; i++)
    {
        if (height[i] > temp)
        {
            temp = height[i];
        }
        else
        {
            cout += temp - height[i];
            printf("L index %d  temp %d add %d\n", i, temp, temp - height[i]);
        }
    }
    printf("cout %d\n", cout);

    temp = 0;
    for (int32_t i = rightIndex; i >= leftIndex; i--)
    {
        if (i < 0)
        {
            break;
        }

        if (height[i] > temp)
        {
            temp = height[i];
        }
        else
        {
            cout -= temp - height[i];
            printf("R index %d  temp %d add %d\n", i, temp, temp - height[i]);
        }
    }
    printf("cout %d\n", cout);

    return abs(cout);
}

int main(int argc, char *argv[])
{

    // 4, 2, 0, 3, 2, 5,
    uint32_t trapMap[] = {
        4, 2, 0, 3, 2, 5
        // 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1

        //
    },
             dataCount = 0, result = 0;

    dataCount = sizeof(trapMap) / sizeof(uint32_t);
    result = trap2(trapMap, dataCount);

    printf("trap %d\n", result);

    return 0;
}